All the problems are in minimization here, i.e. if an objective function \(z(x)\) is actually in maximisation, we will minimise \(-z(x)\) instead. Only binary variables are considered here.

1 Instances

[An explanation of instances and instance names (as in the ReadMe file)]

List of test instances.

Go to instance example

Several methods for generating the coefficient of the objective functions are tested here. This is given by the column coef.

2 Input and output statistics

A set of statistics are stored for each instance and algorithm run.

2.1 Input statistics

For each instance we have the following statistics:

  • Problem class (PC):
    • KP = Knapsack Problem
    • AP = Assignment Problem
    • UFLP = Uncapacited Facility Location Problem
  • \(n\): number of variables.
  • \(p\): number of objectives.
  • rangeC: the range the objective coefficients are generated within
  • coef: the method used for the generation of the objective coefficients (see section Research questions). We have:
    • random = random coefficient generation
    • 2box = two-boxes generation
    • spheredown = generation on the lower part of a sphere (in minimisation)
    • sphereup = generation on the upper part of a sphere (in minimisation)
  • ratioND = proportion of objective coefficient vectors (here considered as a vector in \(\mathbb{R}^p\), one for each variable, defining the objective coefficient for all the objective for this variable) that are non-dominated (with respect to the other objective coefficient vectors).

2.2 Output statistics

For each algorithm run we have the following statistics, that can be found in stat,csv. Some of these are also input statistics but reintroduced as output statistics for a better readability. We have:

  • pb: class of the problem.
  • \(n\): number of variables.
  • \(p\): number of objectives.
  • coef: method for generation of the objective coefficients (see Section Research questions).
  • rangemin: minimum possible value for the objective coefficients.
  • rangemax: maximum possible value for the objective coefficients.
  • nodesel: node selection strategy.
  • varsel: variable selection strategy.
  • OB: objective branching strategy.
  • solved: 1 if the instance is solved within 3600 sec, 0 otherwise.
  • YN: size of YN. If solved = 0, it represent the size of the upper bound set at 3600 sec, when the algorithm stops.
  • nbnodes: number of nodes explored.
  • mindepthT: minimal depth of a leaf node.
  • maxdepthT: maximal depth of a leaf node (and thus of the tree).
  • avgdepthT: average depth of the leaf nodes.
  • avgdepthYN: average depth of the nodes where the non-dominated points were found.
  • nbleaf: number of leaf nodes.
  • nbinfeas: number of nodes pruned by infeasibility.
  • pctinfeas: proportion (in %) of leaf nodes pruned by infeasibility.
  • tpsinfeas: average time spend to prune a node by infeasibility (in msec).
  • nbopt: number of nodes pruned by optimality.
  • pctopt: proportion (in %) of leaf nodes pruned by optimality.
  • tpsopt: average time spend to prune a node by optimality (in msec).
  • nbdomi: number of nodes pruned by dominance.
  • pctdomi: proportion (in %) of leaf nodes pruned by dominance.
  • avgdomi: average time spend to prune a node by dominance (in msec).
  • nbLB: number of lower bound set computed.
  • avgfacets: average number of facets in the lower bound set (i.e. in \(\mathcal{L} + \mathbb{R}^p\)).
  • avgNDf: average number of strictly non-dominated facets.
  • pctavgNDf: proportion (in %) of facets that are strictly non-dominated.
  • avgWNDf: average number of weekly non-dominated facets.
  • pctavgWNDf: proportion (in %) of facets that are weekly non-dominated.
  • maxfacets: maximal number of facets a lower bound set had in the tree.
  • maxNDf: number of strictly non-dominated facets in the lower bound set with the maximal number of facets.
  • pctmaxNDf: proportion (in %) of facets that are strictly non-dominated in the lower bound set with the maximal number of facets.
  • maxWNDf: number of weekly non-dominated facets in the lower bound set with the maximal number of facets.
  • pctmaxWNDf: proportion (in %) of facets that are weekly non-dominated in the lower bound set with the maximal number of facets.
  • tpstotal: CPU time (in sec) used to solve the instance. 3600 if the instance is not solved.
  • tpsLB: CPU time (in sec) used to compute lower bound sets.
  • pcttpsLB: proportion (in %) of the total CPU time spend in the computation of lower bound sets.
  • tpsdomi: CPU time (in sec) used to dominance test when the algorithm has to determine whether a node can be pruned by dominance or not.
  • pcttpsdomi: proportion (in %) of the total CPU time spend in the dominance test when the algorithm has to determine whether a node can be pruned by dominance or not.
  • tpsUB: CPU time (in sec) used to update the upper bound set.
  • pcttpsUB: proportion (in %) of the total CPU time spend in updating the upper bound set.
  • tpsnodesel: CPU time (in sec) used to choose the next node to develop.
  • pcttpsnodesel: proportion (in %) of the total CPU time spend in choosing the next node to develop.
  • tpsvarsel: CPU time (in sec) used to choose the variable to branch on.
  • pcttpsvarsel: proportion (in %) of the total CPU time spend in choosing the variable to branch on.
  • tpsOB: CPU time (in sec) used to create the sub-problems in the objective space, i.e. to compute objective branching. (/! it requires two different steps in total: computing the SLUBs but also do additional dominance test to determine the dominance status of each local upper bounds ! This number take into account the two steps.)
  • pcttpsOB: proportion (in %) of the total CPU time spend in computing objective branching.
  • tpsSLUB: CPU time (in sec) used to compute the super local upper bounds.
  • pcttpsSLUB: proportion (in %) of the total CPU time spend in computing the super local upper bounds.
  • tpsdomiLUB: CPU time (in sec) used to do the additionnal dominance tests to get the dominance status of EACH local upper bound.
  • pcttpsdomiLUB: proportion (in %) of the total CPU time spend in doing the additionnal dominance tests on the local upper bounds.
  • nbOB: number of nodes where two or more sub-problems are created in the objective space. When using the exact objective branching (OB = exact), it in particular shows how often it is actually possible to split the objective space with the definition of the sub-problems that we used (\(z(x) \leqq \bar{z}\), \(\bar{z} \in \mathbb{R}^p\)).
  • pctnbOB: proportion (in %) of the nodes explored that where split in two or more sub-problems in the objective space.
  • avgdepthOB: [relevant only if OB = exact] average depth of the nodes split in two or more sub-problems in the objective space.
  • mindepthOB: [relevant only if OB = exact] minimal depth of the nodes split in two or more sub-problems in the objective space.
  • maxdepthOB: [relevant only if OB = exact] maximal depth of the nodes split in two or more sub-problems in the objective space.
  • avgnbpbOB: [relevant only if OB = exact] average number of sub-problems created in the objective space in the nodes split in two or more sub-problems in the objective space.
  • maxnbpbOB: [relevant only if OB = exact] average number of sub-problems created in the objective space in the nodes split in two or more sub-problems in the objective space.
  • ratioNDcoef: proportion (expressed as a number between 0 and 1) of objective coefficient vectors (here considered as a vector in \(\mathbb{R}^p\), one for each variable, defining the objective coefficient for all the objective for this variable) that are non-dominated (with respect to the other objective coefficient vectors).

For each instance, other statistics can be found in the details folder. We have:

  • <instance>_coef.csv: each row correspond to a variable. The \(p\) first column represent the \(p\) objective coefficients for a given variable. The last column is 1 if the objective coefficient vector is not dominated by another one, 0 otherwise.
  • <instance>_UB.csv: each row represent a \(y \in \mathcal{Y}_N\). The \(p\) first columns represent the values for the \(p\) objective functions. The other columns are redundant information with what comes later and can be ignored.
  • <instances>_XE.csv: each row represent a \(y \in \mathcal{Y}_N\), sorted exactly in the same order as in <instance>_UB.csv. Each column represent the value of a variable, corresponding to the pre-image of the current \(y\).

For each run, statistics on the non-dominated points can be found in the folder UBrun. The names of the files are in the form <instance>_<nodesel>_<varsel>_<OB>_UB.csv, where <instance is the name of the instance, <nodesel> is the node selection strategy (see next section for the names), <varsel> is the variable selection strategy (see next section for the names) and <OB> is the objective branching strategy (-2 for OB = None, 1 for OB = cone, 2 for OB = exact). In this file, each row correspond to a \(y \in \mathcal{Y}_N\). The statistics are the following:

  • the \(p\) first columns correspond the values of the objective functions.
  • node: number of the node where this point has been discovered. The higher this number is, the later the point has been discovered.
  • time: time (in sec) elapsed between the start of the algorithm and when this point has been found (for the first time).
  • depth: depth of the node where this point has been found (for the first time).

3 Research questions

The first purpose of this study is to learn how some components of the branch and bound influences the behaviour of the algorithm it terms of computational time (expressed in seconds everywhere) and in term of number of nodes explored (i.e. how much nodes are developed in the branch and bound tree before the algorithm ends).

The branch and bound algorithm will always use the linear relaxation as lower bound set and the incumbent set as upper bound set. At each nodes, the extreme points of the lower bound set are checked for integrality and possibly added to the upper bound set. The components that will vary are:

The second purpose of this study is to learn how the caracteristics of an instance can affect its difficulty. The difficulty will be here mesured by the size of the non-dominated set, and the computational time required to solve the instance. The computational time will be determined using the branch and bound algorithm previously described. Note that the complexity of an objective space search algorithm is positively correlated to the size of the non-dominated set as the more non-dominated there are, the more integer programs have to be solved.

The focus will be here on the objective function coefficients. The first research question here is: does the range of the objective function coefficient has an impact on the difficulty of the problem ?. In order to answer that, three different ranges will be tested:

For the facility location problems, two sets of costs (i.e. coefficients of objective function) can be identified: the assignment costs (\(c_{ij}\)) and the facility opening costs (\(f_j\)). It is reasonable to assume that these two sets of costs may not take their values in the same range. Let the assignment costs take their values in \([a,b]\), the generation of the facility opening costs will be divided into two categories of instances:

The second research question related to that topic is: does the method used to generate the coefficients of the objective function has an impact on the difficulty of the problem ?. Indeed, the usual procedure to generate objective function is to generate the coefficients randomly in a given range \([a,b]\). However, one could imagine other way to generate coefficient. Four methods will be studied here.

You must enable Javascript to view this page properly.

You must enable Javascript to view this page properly.

You must enable Javascript to view this page properly.

You must enable Javascript to view this page properly.

4 Preliminary tests CPU time

Here are tested different combinations of variable and node selection for the basic branch and bound. In the following :

4.1 Random coefficient generation

The coefficient are generated using the random method.

4.1.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

4.1.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

4.1.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

4.1.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.1.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2 Sphere Down coefficient generation

The coefficient are generated using the spheredown method.

4.2.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

4.2.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

4.2.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

4.2.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.2.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3 Sphere Up coefficient generation

The coefficient are generated using the sphereup method.

4.3.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

4.3.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

4.3.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

4.3.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.3.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4 Two boxes coefficient generation

The coefficient are generated using the random method.

4.4.1 Range : [1,10]

The coefficient of the objective functions are in the range [1,10].

4.4.1.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.1.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.1.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.1.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.2 Range : [1,1000]

The coefficient of the objective functions are in the range [1,1000].

4.4.2.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.2.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.2.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.2.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.3 Range : [1000,2000]

The coefficient of the objective functions are in the range [1000,2000].

4.4.3.1 Knapsack

Knapsack problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.3.2 Assignment

Assignment problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.3.3 Facility location easy

Easy facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

4.4.3.4 Facility location hard

Hard facility location problems are studied here. The table below shows the average computational times in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

The table below shows the average number of nodes explored in function of the size of the problem and of the variable and node selection strategies. The corresponding plot is given afterwards.

5 Study on the coefficients of the objective function

In this section, relations between |YN| and various characteristics of the coefficient of the objective function are studied.

5.1 Knapsack

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

In the plot coming after, the relation between the size of the non-dominated set and the CPU time required to find it with the best configuration previously found is shown.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

5.2 Assignment

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

In the plot coming after, the relation between the size of the non-dominated set and the CPU time required to find it with the best configuration previously found is shown.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

5.3 Facility location easy

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

In the plot coming after, the relation between the size of the non-dominated set and the CPU time required to find it with the best configuration previously found is shown.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

5.4 Facility location hard

The relation between |YN| (x-axis), the proportion of non-dominated objective function coefficients (y-axis) and the number of variables (color-axis) is shown in the next plot.

In the plot coming after, the relation between the size of the non-dominated set and the CPU time required to find it with the best configuration previously found is shown.

The next plots study the impact of the range of the range of the objective function coefficient on |YN|. This is done separately for each coefficient generation methods.

The next plots study the impact of the method used for the generation of the objective function coefficient on |YN|. This is done separately for each possible ranges for the coefficients.

end